package lc476;

public class Lc476_1 {

    /**
     * 1、 先找到位掩码
     * 2、和原码做异或运算，就得到了补数
     * time：O(log num)
     * space: O(1)
     * spend: 10m
     */
    public int findComplement(int num) {
        // 正整数 有符号最高位为0，还剩下31位，1左移30位使其可能的最高位1 也就是1000000000000000000000000000000
        int mask = 1 << 30;
        // 循环找num中的最高位1在哪一位，还剩下31位，1左移30位使其到可能的最高位1
        while((num & mask) == 0){
            mask >>= 1;
        }
        //  然后mask做进以为在建议就得到我们需要的和num位数相同，全1的掩码
        mask = (mask << 1) - 1;
        // 然后异或就是补数
        return num ^ mask;
    }

    public static void main(String[] args) {
        Lc476_1 lc = new Lc476_1();
        lc.findComplement(1);

    }

}
